/*#
 #*/
package cn.itaha.algorithm.leetcode.dynamicprogramming;

/**
 * <p>标题：不同路径II</p>
 * <p>功能：</p>
 * <pre>
 * 其他说明：
 * 地址链接：https://leetcode-cn.com/problems/unique-paths-ii/
 * </pre>
 * <p>创建日期：2019年11月22日下午4:17:30</p>
 * <p>类全名：cn.itaha.algorithm.leetcode.dynamicprogramming.Code63UniquePathsii</p>
 * 查看帮助：<a href="" target="_blank"></a> 
 *
 * 作者：yinjun
 * 初审：
 * 复审：
 * @version 1.0
 */
public class Code63UniquePathsii
{
	public static void main(String[] args)
	{
		/**
		 * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

		机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

		现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
		网格中的障碍物和空位置分别用 1 和 0 来表示。

		说明：m 和 n 的值均不超过 100。

		示例 1:

		输入:
		[
		  [0,0,0],
		  [0,1,0],
		  [0,0,0]
		]
		输出: 2
		解释:
		3x3 网格的正中间有一个障碍物。
		从左上角到右下角一共有 2 条不同的路径：
		1. 向右 -> 向右 -> 向下 -> 向下
		2. 向下 -> 向下 -> 向右 -> 向右

		 */
		int uniquePathsWithObstacles = uniquePathsWithObstacles(new int[][] { { 0, 1, 0, 0, 0 }, { 0, 0, 0, 0, 0 }, { 0, 0, 1, 0, 0 }, { 0, 0, 0, 0, 0 } });
		System.out.println(uniquePathsWithObstacles);
	}

	/**
	 * 本题采用动态规划思路:
	 * 		本题规划思路同无障碍物时相同，可参考Code62UniquePaths类解释
	 * 		障碍物出路径数为0
	 * 		有障碍物，即凡是通过障碍物的路径数都为0，即在无障碍物的基础上，剔除掉所有通过障碍物的路径数
	 * 		障碍物的考虑：{
	 * 					1.障碍物在原点
	 * 					2.障碍物在边界，如何处理边界直线上的路径数？
	 * 					3.障碍物在非边界，如何处理？
	 * 				}
	 * 		障碍物在原点：
	 * 			则直接返回0
	 * 		障碍物在边界：
	 * 			则边界直线上障碍物之后的路径数都为0，可根据障碍物位置处路径数为0，直接将其后面的都设为0
	 * 		障碍物在非边界：
	 * 			则只需要考虑将当前障碍物位置处的路径数设置为0即可
	 * 
	 * 
	 * 
	 * @param obstacleGrid
	 * @return
	 */
	public static int uniquePathsWithObstacles(int[][] obstacleGrid)
	{
		//1.地图为空或不存在，则返回1
		if (obstacleGrid == null || obstacleGrid.length <= 0)
		{
			return 1;
		}
		//2.地图只有一格，且有路障，则直接返回0
		if (obstacleGrid[0][0] == 1)
		{
			return 0;
		}
		/**
		 * [
		 * 	[0,1,0,0,0],
		 * 	[1,0,0,0,0],
		 * 	[0,0,0,0,0],
		 * 	[0,0,0,0,0]
		 * ]
		 */
		//3.初始化dp大小，因为是矩形地图，因此直接用obstacleGrid的长和obstacleGrid[0]的宽
		int m = obstacleGrid.length;
		int n = obstacleGrid[0].length;
		int[][] dp = new int[m][n];
		//4.外层循环控制横向走
		for (int i = 0; i < dp.length; i++)
		{
			//5.内层循环控制纵向走
			for (int j = 0; j < dp[i].length; j++)
			{
				//6.判断如果此坐标有路障，则到达此坐标的路径数为0
				if (obstacleGrid[i][j] == 1)
				{
					dp[i][j] = 0;
					continue;
				}
				//7.如果是初始位置，且无路障，则路径数为1
				if (i == 0 && j == 0)
				{
					dp[i][j] = 1;
					continue;
				}
				//8.即一条路走到黑的情况下，只要有路障，则各个坐标的路径数都为0
				/**
				 * 在i=0或j=0的情况下：
				 * 		dp[i][j - 1] == 0 或 dp[i - 1][j] == 0
				 * 		则表明一路直行的路上必定某个点有路障
				 */
				if ((i == 0 && dp[i][j - 1] == 0) || (j == 0 && dp[i - 1][j] == 0))
				{
					dp[i][j] = 0;
					continue;
				}
				//9.即一条路走到黑的情况下，没有路障，则各个坐标的路径数都为1
				if ((i == 0 && dp[i][j - 1] != 0) || (j == 0 && dp[i - 1][j] != 0))
				{
					dp[i][j] = 1;
					continue;
				}
				//10.不满足以上的条件，走到这时，已然处理好了所有情况，则按照情况相加即可
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
			}
		}
		/**
		 * 循环打印路径数数组
		 */
		for (int i = 0; i < dp.length; i++)
		{
			for (int j = 0; j < dp[i].length; j++)
			{
				System.out.print(dp[i][j] + "\t");
			}
			System.out.println("");
		}
		System.out.println("dp[m-1][n-1]:" + dp[m - 1][n - 1]);
		return dp[m - 1][n - 1];
	}
}
